package com.LeetCode.Array;

import org.junit.Test;

public class nextPermutation {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        int i = len - 2;
        //找到第一个 nums[i+1] > num[i] 的位置
        while(i >=0 && nums[i+1] <= nums[i]){
            i--;
        }

        if(i>=0){
            int j = len - 1;
            //找到第一个大于 nums[i] 的 nums[j]
            while(j >=0 && nums[j] <= nums[i]){
                j--;
            }
            swap(nums,i,j);
        }
        reverse(nums,i+1);
    }

    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    @Test
    public void test(){
        int[] arr = {1,1,5};
        nextPermutation(arr);
        for(int i : arr){
            System.out.print(i + " ");
        }
    }

}
